""""2.用分治法解决最大字段和问题（最大子序列和问题）。
给定n个元素的整数列（可能为负整数）a1，a2 ，…，an。求形如：
ai，ai+1 ，…，aj       i、j=1……n，i<=j
的子段，使其和为最大。当所有整数均为负整数时定义其最大子段和为0。
例如当（a1，a2，a3，a4，a5，a6）=(-2,11,-4,13,-5,-2)时，最大子段和为i=2 ,j=4（下标从1开始）。"""
def max_subarray(nums):
    n = len(nums)

    def helper(low, high):
        if low == high:
            if nums[low] > 0:
                return nums[low], low, low
            else:
                return 0, -1, -1

        mid = (low + high) // 2
        left_max, left_start, left_end = helper(low, mid)
        right_max, right_start, right_end = helper(mid + 1, high)

        left_sum = 0
        tmp = 0
        cross_left = mid
        for i in range(mid, low - 1, -1):
            tmp += nums[i]
            if tmp > left_sum:
                left_sum = tmp
                cross_left = i

        right_sum = 0
        tmp = 0
        cross_right = mid + 1
        for i in range(mid + 1, high + 1):
            tmp += nums[i]
            if tmp > right_sum:
                right_sum = tmp
                cross_right = i

        cross_max = left_sum + right_sum
        if cross_max > 0:
            cross_start, cross_end = cross_left, cross_right
        else:
            cross_max = 0
            cross_start, cross_end = -1, -1

        if left_max >= right_max and left_max >= cross_max:
            return left_max, left_start, left_end
        elif right_max >= left_max and right_max >= cross_max:
            return right_max, right_start, right_end
        else:
            return cross_max, cross_start, cross_end

    max_sum, start, end = helper(0, n - 1)
    if max_sum <= 0:
        return 0, None, None
    else:
        return max_sum, start + 1, end + 1


# 测试示例
if __name__ == '__main__':
    nums = [-2, 11, -4, 13, -5, -2]
    max_sum, start, end = max_subarray(nums)
    print(f"最大子段和为: {max_sum}")
    print(f"起始位置: {start}, 结束位置: {end}")